解題程式碼

var isSubtree = function (root, subRoot) {
  const isSameTree = (p, q) => {
    if (p === null && q === null) return true;
    if (p === null || q === null || p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  };

  if (root === null || subRoot === null) return false;
  if (isSameTree(root, subRoot)) return true;
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

  // 錯誤的思考方向，碰到 root = [1,1], subRoot = [1] 時兩個 root 相同，但就會比較這兩 tree 進而直接回傳 false，而不進到 root 的左子樹
  //   if (root.val === subRoot.val) {
  //     return isSameTree(root, subRoot);
  // } else {
  //     return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
  // }
};

解題思路、演算法

這題使用 DFS，去比對當前的 root 是否和 subRoot 相同，是的話返回 true，否就去遞迴當前 root 的左右子樹是否和 subRoot 相同

至於判斷兩個樹是否相同，則可以參考 100. Same Tree 這題。

解法的時間、空間複雜度

n is the number of nodes in the tree rooted at the root.
m is the number of nodes in the tree rooted at subRoot.

時間複雜度: O(m * n)
空間複雜度: O(m + n)

參考資料

Subtree of Another Tree - Leetcode 572 - Python